#ifndef __NONAME_HASHTABLE_H__
#define __NONAME_HASHTABLE_H__

#define NONAME_LIB_USE

#include <ntifs.h>
#include "nm_mem.h"
#include "algo/crc32.h"

#define HASH_DEFAULT_CAP	128

template< class VAL >
class khashtable {

public:
	BOOLEAN Init( ULONG Size = HASH_DEFAULT_CAP );
	BOOLEAN Resize( ULONG Size = HASH_DEFAULT_CAP );
	BOOLEAN Insert( PVOID KeyBuffer, ULONG Length, const VAL& Value );
	BOOLEAN Remove( PVOID KeyBuffer, ULONG Length );
	VAL* Find( PVOID KeyBuffer, ULONG Length );
	void Clear();

	ULONG GetHashTableSize() { return m_HashSize; }
	ULONG GetHashedCount() { return m_HashedCount; }
	ULONG GetConflictCount() { return m_ConflictCount; }
	ULONG GetMaxConflictDepth() { return m_MaxConflictDepth; }

	khashtable() { Init( HASH_DEFAULT_CAP ); }
	void Release() { Clear(); }


private:

	ULONG DoHash( PVOID KeyBuffer, ULONG Length );

	struct _HASH_NODE {
		/* is Value set ? */
		BOOLEAN ValSet;
		/* conflict link */
		struct _HASH_NODE* Next;
		/* conflicts may exist, so _Key is also needed */
		PVOID Key; 
		VAL Value;
	public:
		_HASH_NODE() : ValSet( FALSE ), Next( NULL ), Key(NULL) {}
	};

	typedef struct _HASH_NODE HASH_NODE;

	ULONG m_HashSize, m_HashedCount;
	ULONG m_ConflictCount, m_MaxConflictDepth;
	HASH_NODE m_HashTable;

};

template< class VAL >
ULONG khashtable<VAL>::DoHash( PVOID KeyBuffer, ULONG Length )
{
	ULONG crc32;

	crc32Init(&crc32);
	crc32Update(&crc32, KeyBuffer, Length);
	crc32Finish(&crc32);

	return crc32 % m_HashSize;
}
template< class VAL >
BOOLEAN khashtable< VAL >::Init( ULONG Size /*= HASH_DEFAULT_CAP*/ )
{

	if( m_HashTable != NULL ) {

		return resize( Size );
	}


	m_HashTable = new HASH_NODE[ Size ];

	m_ConflictCount = 0;
	m_MaxConflictDepth = 0;
	m_HashSize = Size;
	m_HashedCount = 0,
		return TRUE;
}

template< class VAL >
BOOLEAN khashtable< VAL >::Resize( ULONG Size /*= HASH_DEFAULT_CAP*/ )
{
	if( Size == m_HashSize ) {
		return TRUE;
	}

	if( m_HashTable != NULL ) {

		Clear();
		m_HashTable = NULL;
	}
	return Init( Size );
}

template< class VAL >
BOOLEAN khashtable< VAL >::Insert( PVOID KeyBuffer, ULONG Length, const VAL& Value )
{
	ULONG key;
	HASH_NODE *node;
	ULONG depth;
	HASH_NODE *pn;

	if( m_HashTable == NULL ) {

		return FALSE;
	}

	key = DoHash( KeyBuffer, Length );

	if( !m_HashTable[ key ].ValSet ) {
		m_HashTable[ key ].ValSet = TRUE;
		m_HashTable[ key ].Key = new UCHAR[Length];
		memcpy(m_HashTable[ key ].Key, KeyBuffer, Length);
		m_HashTable[ key ].Value = Value;
		return ++m_HashedCount, TRUE;
	} else if( memcmp(m_HashTable[ key ].Key, KeyBuffer, Length) == 0) {

		return TRUE;
	}

	/* walk thru the conflict list */
	node = &m_HashTable[ key ];

	for(depth = 1 ; node->Next != NULL; depth++ ) {
		if( memcmp(node->Key, KeyBuffer, Length) == 0 ) {
			return TRUE;
		}

		node = node->Next;
	}

	if( memcmp(node->Key, KeyBuffer, Length) == 0 ) {
		return TRUE;
	}

	/* create conflict node */
	pn = new HASH_NODE;

	pn->Key = new UCHAR[Length];
	memcpy(pn->Key, KeyBuffer, Length);
	pn->Value = Value;
	pn->ValSet = TRUE;
	node->Next = pn;

#ifndef max
# define max(a,b)    (((a) > (b)) ? (a) : (b))
#endif

	m_ConflictCount++;
	m_HashedCount++;
	m_MaxConflictDepth = max( m_MaxConflictDepth, depth );
	return TRUE;
}

template< class VAL >
BOOLEAN khashtable< VAL >::Remove( PVOID KeyBuffer, ULONG Length )
{
	ULONG key;
	HASH_NODE *tmp;
	HASH_NODE *node;
	HASH_NODE *nxt; 

	if( m_HashTable == NULL ) {
		return FALSE;
	}

	key = DoHash( KeyBuffer, Length );

	if( m_HashTable[ key ].ValSet && memcmp(m_HashTable[ key ].Key, KeyBuffer, Length) == 0 ) {

		m_HashedCount--;

		if (m_HashTable[ key ].Key != NULL) {

			delete m_HashTable[ key ].Key;
			m_HashTable[ key ].Key = NULL;
		}

		tmp = m_HashTable[ key ].Next;
		if( tmp == NULL) {
			m_HashTable[ key ].Value = 0;	/* this may destruct some instance */
			m_HashTable[ key ].ValSet = FALSE;

			return TRUE;
		}

		m_HashTable[ key ].Key = tmp->Key;
		m_HashTable[ key ].Value = tmp->Value;
		m_HashTable[ key ].Next = tmp->Next;

		delete tmp;

		return TRUE;
	}

	node = &m_HashTable[ key ];
	while( node->Next != NULL ) {
		nxt = node->Next;
		if( nxt->ValSet && memcmp(nxt->Key, KeyBuffer, Length) == 0 ) {
			m_HashedCount--;
			node->Next = nxt->Next;

			if (nxt->Key != NULL) {
				delete nxt->Key;
			}

			delete nxt;

			return TRUE;
		}

		node = nxt;
	}

	return FALSE;
}

template< class VAL >
VAL* khashtable< VAL >::Find( PVOID KeyBuffer, ULONG Length )
{
	ULONG key;
	HASH_NODE *node ;

	if( m_HashTable == NULL ) {
		return FALSE;
	}

	key = DoHash( KeyBuffer, Length );
	node = &m_HashTable[ key ];

	do {
		if( node->ValSet && memcmp(node->Key, KeyBuffer, Length) == 0 ) {
			return &node->Value;
		}

		node = node->Next;
	} while( node != NULL );

	return NULL;
}

template< class VAL >
void khashtable< VAL >::Clear()
{
	ULONG i;
	HASH_NODE *node;
	HASH_NODE* tmp;

	if( m_HashTable == NULL )
		return ;

	for( i = 0; i < m_HashSize; i++ ) {

		if (m_HashTable[i].ValSet && m_HashTable[i].Key != NULL) {

			delete m_HashTable[i].Key;
			m_HashTable[i].Key = NULL;
		}
		m_HashTable[i].ValSet = FALSE;
		node = m_HashTable[i].Next;
		while( node != NULL) {

			tmp = node;
			node = node->Next;

			if (tmp->ValSet && tmp->Key != NULL) {

				delete tmp->Key;
			}
			delete tmp;
		}
	}

	delete[] m_HashTable;

	m_HashTable = NULL;
	m_HashedCount = 0;
	m_ConflictCount = 0;
	m_MaxConflictDepth = 0;
}


#endif